#include <iostream>
#include <set>
#include <fstream>
#include <cstdlib>
#include <queue>
#include <string>
#include <cstring>
#include <sstream>
#include <map>
#include <stack>
#include <vector>
using namespace std;

char WenFaPath[] = "D:/wenfa.txt";//文法路径
char OldTablePath[] = "D:/table.txt";//书写预测分析表txt路径
char NewTablePath[] = "D:/table.csv";//将txt分析表改成CSV的新路径
char TokenPath[]="D:/b.txt";//TOKEN序列路径

set <string> Zhongjie;
set <string> Feizhong;
map <string,set<string> > FIRST;
map <string,set<string> > FOLLOW;
string wenfa[85][2];
vector<vector<string> > table;
int wenfaCounts =0;
int Row=0;
int Line=0;
queue<string> Token;

void Deal_Wenfa();
bool In_Zhongjie(string x);
bool In_Feizhong(string x);

void Create_First();
set<string> Get_Right(string x);
bool StrInSet(string x, set<string> y);
set<string> AddSet(set<string> x,set<string> y);
set<string> AddSet(set<string> x,set<string> y,bool j);
bool CompareSet(set<string> x,set<string> y);
bool CompareSet(set<string> x,set<string> y,bool j);
void WriteFirst();

void Creat_Follow();
void WriteFollow();

void CreateTable();
void WriteTable();
set<string> Get_FIRST(string r);
string FindTable(string x,string y);//查表

void ReadToken();
bool IsNumber(char x);
void FenXi();
string PrintStack(stack<string> x);

bool In_Zhongjie(string x){
    bool result = false;
    for(string t :Zhongjie){
        if(t.length() != x.length() ) continue;
        
        result =true;
        
        for(int i =0 ; i < t.length();i++){
            if(x[i] !=t[i])
              result = false;
        }
        if(result)
           break;
    }

    return result;
}
bool In_Feizhong(string x){    
    bool result = false;

    for(string t :Feizhong){
        if(t.length() != x.length() ) continue;
        result =true;
        
        for(int i =0 ; i < t.length();i++){
            if(x[i] !=t[i])
              result = false;
        }
        if(result)
           break;
    }
    return result;
}

int main(){
    
    Deal_Wenfa();
    Create_First();
    WriteFirst();
    Creat_Follow();
    WriteFollow();
    CreateTable();
    WriteTable();
    ReadToken();
    FenXi();
    return 0;
}



void Deal_Wenfa(){
    ifstream WenfaFile;
    cin.unsetf(ios::skipws);
    WenfaFile.open(WenFaPath,ios::in);
    if( ! WenfaFile.is_open()){
        cout << "open file erro"<<endl;
        return ;
    }
   // cout <<"open file corrte"<<endl;
    string s ;
    int i =0;
    while(! WenfaFile.eof()){   // 分割文法，放入二维数组中存储
        getline(WenfaFile,s);
        //cout <<s<<endl;
        bool judge = true;
        for(int j =0 ;j <s.length(); j ++){
            if(s[j]=='-'&&s[j+1] =='>'){
                judge = false;
                j+=3;
            }
            if(judge){  
                if(s[j]!=' ')
                  wenfa[i][0]+=s[j];
            }
            else wenfa[i][1] +=s[j];
        }
        //cout <<wenfa[i][0]<<"||"<<wenfa[i][1]<<endl;
        judge = true;
        i++;
    }

    for(int j =0 ; j <85; j ++){  // 构建非中介符号集
        
        Feizhong.insert(wenfa[j][0]);
    }

    for(int j =0; j <85; j++){// 构建终结符符号集
        istringstream str(wenfa[j][1]);
        string out ;
        while(str.good()){   //把字符串按空格分开
            getline(str,out,' ');
            if(!out.empty()&& ( !In_Feizhong(out))){
                Zhongjie.insert(out);
            }
        }
       
    }
    return ;
}

void Create_First(){//构造FIRST集合
    bool change = true;
    cout << " in create first"<<endl;
    while(change ){
        change = false;
        for(string x:Feizhong){
            //cout << x<<" 更新: ";

            set <string> Right ;
            Right = Get_Right(x);
            set <string> first = FIRST[x];
            for(string r:Right){
                if(r.compare("$")==0 && (!StrInSet("$",first)||first.empty()) ){
                    first.insert(r);
                    change = true ;
                }
                else{
                    istringstream str(r);
                    string ou ;
                    bool R= true;
                    while(str.good()){
                       getline(str,ou,' '); 
                       string out = ou;
                       if(In_Feizhong(out) && FIRST[out].empty() ){
                           change = true;
                           break;
                       }
                       else if(In_Zhongjie(out) ){
                           first.insert(out);
                           if( (!StrInSet(out,first)||first.empty()) )
                               change = true;
                           break;
                       }
                       else if(In_Feizhong(out)){
                           if( !CompareSet(first,FIRST[out]) ){
                               change = true;
                               if(StrInSet("$",FIRST[out])&& !str.good()){//////////判断最后一个
                                   first = AddSet(first,FIRST[out]);
                               }
                               else if(StrInSet("$",FIRST[out])){
                                   first = AddSet(first,FIRST[out],true);
                                   continue;
                               }
                               else if(!StrInSet("$",FIRST[out])){
                                   first = AddSet(first,FIRST[out]);
                                   break;
                               }
                           }
                           else{
                               change = false;
                               break;
                           }

                       }
                       else{
                           change = false;
                       }

                    }
                    //cout <<" " <<change <<endl;

                }
            }

            FIRST[x]=first;
            
        }

    }

    for(string x:Zhongjie){
        set<string> temp ;
        temp.insert(x);
        FIRST[x]=temp;
    }

}

set<string> Get_Right(string x){
    set <string> result;
    for(int i =0 ; i < 85; i ++){
        if(wenfa[i][0].compare(x)==0)
           result.insert(wenfa[i][1]);
    }
    return result;
}
bool StrInSet(string x, set<string> y){//若X属于集合Y则返回TRUE
    if(y.empty())
      return false;
    bool result = false;
    for(string i :y)
      if(i.compare(x)==0)
         result = true;
    return result;
}

set<string> AddSet(set<string> x,set<string> y){
    for(string i:y)
      x.insert(i);
    return x;
}
set<string> AddSet(set<string> x,set<string> y,bool j){
    if(j) 
     y.erase("$");
    x=AddSet(x,y);
    return x;
}
bool CompareSet(set<string> x,set<string> y){//如果Y包含于X返回TRUE
    bool result = true;
    for(string i:y)
      if( ! StrInSet(i,x))
        result = false;
    return result ;
}
bool CompareSet(set<string> x,set<string> y,bool j){//去掉Y中$如果Y包含于X返回TRUE
    if(j)
      y.erase("$");
    
    return CompareSet(x,y);
}
void WriteFirst(){
    cout<<"FIRST:"<<endl;
    for(string x:Feizhong){
           set<string> temp = FIRST[x];
           cout << x<<":";
           for(string y :temp)
            cout <<y <<"  "; 
           cout <<endl;
     }
     for(string x:Zhongjie){
        set<string> temp= FIRST[x] ;
        cout << x<<":";
           for(string y :temp)
            cout <<y <<"  "; 
           cout <<endl;
    }

}

void Creat_Follow(){
    set <string> s;
    s.insert("#");
    FOLLOW["S"] = s;
    //FOLLOW["iteration_stmt"] = s;

    bool change = true ;
    int test = 15;

    while(change&&test ){
        test --;
        change = false;

        for(string x:Feizhong){//遍历更新非终结符集合
            set <string> Right ;
            Right = Get_Right(x);
            set <string> follow = FOLLOW[x];
            for(string r:Right){  //  产生式集合
                stack <string> temp;
                queue <string> temp2;
                istringstream str(r);
                string ou ;
                //cout <<x<<" : ";

                while(str.good()){
                     getline(str,ou,' '); 
                     temp.push(ou);
                     temp2.push(ou);
                }
                int t = temp2.size();
                string right[t];
                int counts = 0;
                for(int  i=0  ; i < t; i ++){
                    if(temp2.front().compare(" ") != 0&& temp2.front().compare("\n") != 0&& temp2.front().compare("") != 0&& temp2.front().length() > 0&& temp2.front().compare("\r") != 0){
                        right[counts] = temp2.front();
                        //cout <<right[counts]<<"|";
                        counts ++;
                    }
                    temp2.pop();
                }
                t = counts ;
               // cout <<" counts"<<t<<" ";
                 for(int i =0 ; i < t ; i++){ //对该式子进行遍历，其中每个成员更新
                    if( i==t-1 && In_Feizhong(right[i] ) && ( !CompareSet(FOLLOW[ right[i] ],FOLLOW[x])||FOLLOW[ right[i] ].empty() ) )  {
                        //非终结符，最后一个，
                       // cout<<"F"<<x<<" update "<<right[i]<<endl;
                        change = true;
                        FOLLOW[ right[i] ] = AddSet(FOLLOW[ right[i] ],FOLLOW[x]);                             
                    }
                    else if(In_Feizhong(right[i]) &&i<t-1 ){   //非最后一个非终结符号
                        if(In_Feizhong(right[i+1] )){
                            //cout <<" FeiZhongJie : "<<right[i]<<" : ";
                            for(int j = i+1; j < t;j++){
                               // cout <<" FZJ: "<<right[j]<<" ";
                                if( In_Feizhong(right[j])  && (!CompareSet(FOLLOW[ right[i] ],FIRST[x],true) || FOLLOW[ right[i] ].empty())){
                                    change = true;
                                     FOLLOW[ right[i] ] = AddSet(FOLLOW[ right[i] ],FIRST[x],true);  
                                }
                                if(!StrInSet("$",FIRST[right[j]])){
                                    //cout <<" break "<<endl;
                                    break;
                                }
                            }

                        }
                        else{
                            if( !StrInSet(right[i+1] ,FOLLOW[right[i]]) || FOLLOW[ right[i] ].empty()  ){
                               // cout << right[i]<<" add new "<<right[i+1]<<"!"<<endl;
                                change = true;
                                FOLLOW[ right[i] ] = AddSet(FOLLOW[ right[i] ],FIRST[right[i+1]]);
                            }
                        }
                    }
                    else{
                        continue;
                    }
                }

            }
            
        } 

        
    }
    return ;

}
void WriteFollow(){
    cout <<"FOLLOW:"<<endl;
    for(string x:Feizhong){
           set<string> temp = FOLLOW[x];
           cout << x<<":";
           for(string y :temp)
            cout <<y <<"  "; 
           cout <<endl;
     }

}

void CreateTable(){
    queue <string> temp;
    int x = 0;
    for(string tx:Zhongjie){
        temp.push(tx);
        x++;
    }
    string row0[x+1];
    row0[0]="";

    for(int i =1;i<x+1;i++){
        row0[i]=temp.front();
        temp.pop();
    }

    vector<string> r0 (row0,row0+x+1);
    Row = x+1;
    table.push_back(r0);
    int y =1;
    for(string FZ:Feizhong){
        vector<string> tempVector;
        set<string> Right = Get_Right(FZ);
        tempVector.push_back(FZ);

        for(int j =1; j < Row;j++){
            bool judge = true;
            int writecounts = 0;
            string tempa = r0.at(j);
            //cout <<tempa+":" ;
            for(string r:Right){
                if(FIRST[r].empty()){
                    FIRST[r]= Get_FIRST(r);
                }
                if( StrInSet(tempa,FIRST[r]) || ( StrInSet("$",FIRST[r]) && StrInSet(tempa,FOLLOW[FZ]) && r.compare("$")!=0 )   ){
                    judge = false;
                    writecounts++;
                    tempVector.push_back(FZ+"->"+r);
                    break;
                }
            }
            
            if(writecounts==0){
                tempVector.push_back("");
            }
        }
        table.push_back(tempVector);
        y++;

    }
    Line =y;
    return ;

}
void WriteTable(){
    ofstream Writer;
    Writer.open(OldTablePath,ios::out);
    for(vector<string> x:table){
        for(string y:x){
            if(y.length()>0){
                Writer<<"\""+y+"\""<<",";
            }
            else{
                Writer<<"\" \""<<",";
            }

        }
        Writer<<endl;

    }
    Writer.close();
    remove(NewTablePath);
    rename(OldTablePath,NewTablePath);
    return ;
}
set<string> Get_FIRST(string r){
    set<string> result;
    queue <string> temp2;
    istringstream str(r);
    string ou ;
    while(str.good()){
         getline(str,ou,' '); 
         temp2.push(ou);
    }
    int t = temp2.size();
    string right[t];
    int counts = 0;
    for(int  i=0  ; i < t; i ++){
        if( temp2.front().length() > 0){
            right[counts] = temp2.front();
            counts ++;
        }
        temp2.pop();
    }
    t = counts ;
    for(int i =0 ; i < t;i ++){
        if( i == t-1){
            result = AddSet(result,FIRST[right[i]]);
        }
        else if(In_Zhongjie(right[i])){
            result = AddSet(result,FIRST[right[i]]);
            break;
        }
        else if(In_Feizhong(right[i])){
            result = AddSet(result,FIRST[right[i]],true);
            if(!StrInSet("$",FIRST[right[i]])){
                break;
            }
        }
    }
    return result;

}

void ReadToken(){
    ifstream TokenFile;
    cin.unsetf(ios::skipws);
    TokenFile.open(TokenPath,ios::in);
    if( ! TokenFile.is_open()){
        cout << "open file erro"<<endl;
        return ;
    }

    string s ;
    int i =0;
    while(! TokenFile.eof()){   // 分割TOEKN ，获得相应的符号序列
        getline(TokenFile,s);
        if(s.empty())
          break;
        string temp1;
        string temp2;
        for(int j =0 ;j <s.length(); j ++){
            if(s[j]==' '&&s[j+1]=='<' ){
                temp1 = s.substr(0,j);
                temp2 = s.substr(j+2,s.length()-j);
            }      
        }

        for(int j =0; j <temp2.length() ;j++){
            if(temp2[j] ==','){
                temp2 = temp2.substr(0,j);
                break;
            }
        }
        i++;

        if(temp2.compare("IDN")==0){
            Token.push("IDN");
        }
        else if(temp2.compare("CONST")==0){
            if(temp1.length()==1){
                if(IsNumber(temp1[0])){
                    Token.push("INT");
                }
                else{
                    Token.push("CHAR");
                }
            }
            else{
                bool IsInt = true;
                int countsn =0;
                int point =0;
                int e = 0;
                for(int k =0; k < temp1.length(); k ++){
                    if(! IsNumber(temp1[k])){
                       IsInt =false;
                       countsn ++;
                    }

                    if(temp1[k] == '.'){
                        point ++;
                        countsn++;
                    }
                    if(temp1[k] == 'e'&&point <=1){
                        e++;
                        countsn++;
                    }
                }

                if(IsInt){
                    Token.push("INT");
                }
                else if( (countsn == 2&&e==1&&point==1)||( countsn==1&&e==1 )||(countsn ==1&& point==1) ){
                    Token.push("FLOAT");
                }
                else{
                    Token.push("STR");
                }
                
            }

        }
        else{
            Token.push(temp1);
        }


    }
    cout <<i<<endl;

    return ;
    
}
bool IsNumber(char x){
    return (x>='0'&& x<='9');
}
void FenXi(){
    string ZhanDing;
    string TokenDing;
    stack<string> FuHao;
    queue<string> TempToken =Token;
    string ShiZi;
    FuHao.push("S");

    //zhanDing-TokenDing 十个空格 Fuhao栈 十个空格 ShiZi
    while(!Token.empty()){
        ZhanDing = FuHao.top();
        TokenDing = TempToken.front();
        

        if(ZhanDing.compare(TokenDing) == 0){
            cout <<ZhanDing+"-"+TokenDing+"          "+PrintStack(FuHao)+"         pass"<<endl;

            FuHao.pop();
            TempToken.pop();
        }
        else{
            ShiZi =FindTable(ZhanDing,TokenDing);
            cout <<ZhanDing+"-"+TokenDing+"          "+PrintStack(FuHao)+"         "+ShiZi<<endl;
            string tempright;
            
            
            for(int i =0 ; i < ShiZi.length();i++){
                if(ShiZi[i]=='-'&&ShiZi[i+1]=='>'){
                   
                    tempright = ShiZi.substr(i+2,ShiZi.length()-i-2);
                    
                }
            }
            
            stack<string> tempstack ;
            istringstream str(tempright);
            string out;
            while(str.good()){
                getline(str,out,' ');
                if(out.length()>0)
                  tempstack.push(out);
            }
            
            FuHao.pop();
            while(!tempstack.empty()){
                if(! ( tempstack.top().compare("$") ==0 ) )
                   FuHao.push(tempstack.top());
                
                tempstack.pop();
            }
            
            

        }
    
        
    }

    return;
}
string FindTable(string x,string y){
    string  result;
    vector<vector<string> > tempTable = table;
    vector<string> row0 = tempTable.front();
    int j = 0;

    for(int i=1 ; i < row0.size();i++){
        if(y.compare(row0.at(i)) ==0){
            j =i;
        }
    }
    for(int i =1; i < tempTable.size();i++){
        vector<string> temprow = tempTable.at(i);
        if(x.compare(temprow.at(0)) == 0 ){
            result = temprow.at(j);
            if(result.length()<1 )
              result=FindTable(x,"$");
        }

    }
    return result;
}

string PrintStack(stack<string> x){
    string result; 
    while(!x.empty()){
        result+=(x.top() + " "  );
        x.pop();
    }


    return result;
}
